#include <iostream>
using namespace std;

class Link {
public:
    int data;
    Link *next;

    // 构造函数
    Link(int data = 0, Link *next = nullptr) : data(data), next(next) {}
};

class LinkedList {
public:
    Link *head;

    // 构造函数
    LinkedList() : head(nullptr) {}

    // 析构函数
    ~LinkedList() {
        clear();
    }

    // 清空链表
    void clear() {
        Link *current = head;
        while (current != nullptr) {
            Link *next = current->next;
            delete current;
            current = next;
        }
        head = nullptr;
    }

    // 创建链表
    void hcreat() {
        int value;
        cout << "输入多个结点数值,以空格为间隔,以0为终止符: \n";
        while (cin >> value && value != 0) {
            Link *newNode = new Link(value);
            if (head == nullptr) {
                head = newNode;
            } else {
                Link *current = head;
                while (current->next != nullptr) {
                    current = current->next;
                }
                current->next = newNode;
            }
        }
    }

    // 打印链表
    void print() {
        Link *current = head;
        while (current != nullptr) {
            cout << current->data << "->";
            current = current->next;
        }
        cout << "nullptr" << endl;
    }

    // 查找元素
    Link* locate(int x) {
        Link *current = head;
        while (current != nullptr) {
            if (current->data == x) {
                return current;
            }
            current = current->next;
        }
        return nullptr;
    }

    // 删除元素
    void deletel(int x) {
        if (head == nullptr) {
            cout << "链表为空" << endl;
            return;
        }
        if (head->data == x) {
            Link *temp = head;
            head = head->next;
            delete temp;
            return;
        }
        Link *current = head;
        while (current->next != nullptr && current->next->data != x) {
            current = current->next;
        }
        if (current->next == nullptr) {
            cout << "元素 " << x << " 不在链表中" << endl;
            return;
        }
        Link *temp = current->next;
        current->next = temp->next;
        delete temp;
    }

    // 插入元素(后)
    void insertBehind(int x, int y) {
        Link *current = locate(x);
        if (current == nullptr) {
            cout << "元素 " << x << " 不在链表中" << endl;
            return;
        }
        Link *newNode = new Link(y);
        newNode->next = current->next;
        current->next = newNode;
    }

    // 插入元素(前)
    void insertBefore(int x, int y) {
        Link *current = locate(x);
        if (current == nullptr) {
            cout << "元素 " << x << " 不在链表中" << endl;
            return;
        }
        Link *newNode = new Link(y);
        if (current == head) {
            // 如果当前元素是头节点，将新节点设为新的头节点
            newNode->next = head;
            head = newNode;
        } else {
            // 否则，找到当前元素的前一个节点
            Link *previous = head;
            while (previous->next != current) {
                previous = previous->next;
            }
            // 将新节点插入到当前元素之前
            newNode->next = current;
            previous->next = newNode;
        }
    }    
    
    // 修改元素
    void change(int x, int y) {
        Link *current = locate(x);
        if (current == nullptr) {
            cout << "元素 " << x << " 不在链表中" << endl;
            return;
        }
        current->data = y;
    }
};

int main() {
    LinkedList list;

    // 创建链表
    list.hcreat();
    cout << "初始链表为：\n";
    list.print();

    // 删除元素
    int deleteValue;
    cout << "请输入要删除的元素: ";
    cin >> deleteValue;
    list.deletel(deleteValue);
    cout << "删除后链表为：\n";
    list.print();

    // 插入元素
    int insertValue1, insertValue2, signal;
    cout << "请输入插入位置的元素值和标志（0将待插元素插入到它的后面,1将待插元素插入到它的前面）: ";
    cin >> insertValue1 >> signal;

    // 先读取待插元素值
    cout << "请输入待插元素值: ";
    cin >> insertValue2;

    if (signal == 0) {
        list.insertBehind(insertValue1, insertValue2);
    } else if (signal == 1) {
        list.insertBefore(insertValue1, insertValue2);
    } else {
        cout << "输入错误，请重新输入！" << endl;
        return 0;
    }

    cout << "插入后链表为：\n";
    list.print();

    // 修改元素
    int changeValue1, changeValue2;
    cout << "请输入要修改前，后的元素值：";
    cin >> changeValue1 >> changeValue2;
    list.change(changeValue1, changeValue2);
    cout << "修改后链表为：\n";
    list.print();

    return 0;
}